0688. 骑士在棋盘上的概率【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始的，所以左上单元格是 (0,0)，右下单元格是 (n - 1, n - 1)。

象棋骑士有 8 种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从 8 种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回骑士在棋盘停止移动后仍留在棋盘上的概率。

---

示例 1：

输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

---

示例 2：

输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000

---

提示：

• 1 <= n <= 25
• 0 <= k <= 100
• 0 <= row, column <= n - 1

2. 🎯 s.1 - 动态规划

c

double knightProbability(int n, int k, int row, int column) {
    int dirs[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
    double** dp = (double**)malloc(sizeof(double*) * n);
    double** next = (double**)malloc(sizeof(double*) * n);
    for (int i = 0; i < n; i++) {
        dp[i] = (double*)calloc(n, sizeof(double));
        next[i] = (double*)calloc(n, sizeof(double));
    }
    dp[row][column] = 1.0;
    for (int step = 0; step < k; step++) {
        for (int i = 0; i < n; i++) memset(next[i], 0, sizeof(double) * n);
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) {
                if (dp[r][c] == 0) continue;
                for (int d = 0; d < 8; d++) {
                    int nr = r + dirs[d][0], nc = c + dirs[d][1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n)
                        next[nr][nc] += dp[r][c] / 8.0;
                }
            }
        double** tmp = dp; dp = next; next = tmp;
    }
    double res = 0;
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++) res += dp[r][c];
    for (int i = 0; i < n; i++) { free(dp[i]); free(next[i]); }
    free(dp); free(next);
    return res;
}

js

/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function (n, k, row, column) {
  const dirs = [
    [-2, -1],
    [-2, 1],
    [-1, -2],
    [-1, 2],
    [1, -2],
    [1, 2],
    [2, -1],
    [2, 1],
  ]
  let dp = Array.from({ length: n }, () => new Array(n).fill(0))
  dp[row][column] = 1
  for (let step = 0; step < k; step++) {
    const next = Array.from({ length: n }, () => new Array(n).fill(0))
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (dp[r][c] === 0) continue
        for (const [dr, dc] of dirs) {
          const nr = r + dr,
            nc = c + dc
          if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
            next[nr][nc] += dp[r][c] / 8
          }
        }
      }
    }
    dp = next
  }
  let res = 0
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) res += dp[r][c]
  return res
}

py

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dirs = [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
        dp = [[0.0] * n for _ in range(n)]
        dp[row][column] = 1.0
        for _ in range(k):
            nxt = [[0.0] * n for _ in range(n)]
            for r in range(n):
                for c in range(n):
                    if dp[r][c] == 0:
                        continue
                    for dr, dc in dirs:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < n and 0 <= nc < n:
                            nxt[nr][nc] += dp[r][c] / 8
            dp = nxt
        return sum(dp[r][c] for r in range(n) for c in range(n))

• 时间复杂度：$O(k\times n^2)$
• 空间复杂度：$O(n^2)$

算法思路：

• dp[r][c] 表示经过若干步后骑士在 (r,c) 的概率
• 每一步，将当前位置的概率平均分配给 8 个可能的下一位置
• k 步后棋盘上所有概率之和即为答案